"""
题目：https://leetcode-cn.com/problems/intersection-of-two-linked-lists/
    给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。
    题目数据 保证 整个链式结构中不存在环。
    输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,6,1,8,4,5], skipA = 2, skipB = 3
    输出：Intersected at '8'
    解释：相交节点的值为 8 （注意，如果两个链表相交则不能为 0）。
    从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,6,1,8,4,5]。
    在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。

思路：双指针法。如果没有headA或者没有headB，则一定没有相交节点。否则，将两个链表的头结点分别赋值给pa,pb，如果pa与pb不相等，则分别将其后移一位，
     如果pa到了链表尾，则将headB赋值给pa，同理将headB赋值给pb。最终返回pa即可。
时间复杂度：O(m+n)
空间复杂度：O(1)
"""
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
        if not headA or not headB:
            return 0
        pa,pb = headA,headB
        while pa != pb:
            pa = pa.next if pa else headB
            pb = pb.next if pb else headA
        return pa